package datastructre;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("容量必须大于0");
        }
        this.capacity = capacity;
        this.heap = new int[capacity];
    }

    public int[] getHeap() {
        return heap;
    }

    public int getCapacity() {
        return capacity;
    }

    public int getSize() {
        return size;
    }


    public void setSize(int size) {
        this.size = size;
    }

    /**
     * 获取父节点数组索引, 左子节点索引, 右子节点索引
     * 下标从0开始,父节点为 (i-1)/2, 左子节点i*2+1, 右子节点 i*2+2
     */
    private int parent(int child) {
        return (child - 1) / 2;
    }

    private int leftChild(int parent) {
        return parent * 2 + 1;
    }

    private int rightChild(int parent) {
        return parent * 2 + 2;
    }

    private void swap(int i, int j) {
        int temp = this.heap[i];
        this.heap[i] = this.heap[j];
        this.heap[j] = temp;
    }

    public MinHeap insert(int element) {
        if (this.size == this.capacity) {
            if (element <= this.heap[0]) {
                throw new RuntimeException("minHeap is full");
            }
            this.heap[0] = element;
            int cur = 0;
            int smallest=0;
            while (true) {
//                int smallest = this.heap[cur] <= this.heap[this.leftChild(cur)] ? cur : this.leftChild(cur);
//                smallest = this.heap[smallest] <= this.heap[this.rightChild(cur)] ? smallest : this.rightChild(cur);
                if (this.leftChild(cur)<this.size) {
                    smallest = this.heap[cur] <= this.heap[this.leftChild(cur)] ? cur : this.leftChild(cur);
                }
                if (this.rightChild(cur)<this.size) {
                    smallest = this.heap[smallest] <= this.heap[this.rightChild(cur)] ? smallest : this.rightChild(cur);
                }

                if (smallest == cur) {
                    break;
                }
                this.swap(cur, smallest);
                cur = smallest;
            }
        } else {
            this.heap[this.size] = element;
            int cur = this.size;
            /**
             * 默认添加在最下面一层, 如果不是最大值一层, 需上浮
             */

            while (this.heap[cur] < this.heap[this.parent(cur)]) {
                swap(cur, this.parent(cur));
                cur = this.parent(cur);
            }
            this.size++;
        }

        return this;
    }

    @Override
    public String toString() {
        return "MinHeap{" +
                "heap=" + Arrays.toString(heap) +
                '}';
    }

    public static void main(String[] args) {
        /**
        MinHeap minHeap = new MinHeap(100);
        System.out.println("minHeap = " + minHeap);

        int[] nums = new int[100];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i;
        }
        for (int i = 0; i < 1000000000; i++) {
            minHeap.insert(i);
        }
        System.out.println("minHeap = " + minHeap);
        */

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int capacity=10;
        for (int i = 0; i < 20; i++) {
            if (minHeap.size()<capacity) {
                minHeap.offer(i);
            } else if(i>minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(i);
            }
        }

        System.out.println("minHeap = " + minHeap);

    }
}
